#include<vector>
#include<queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    struct WrapNode {
        int depth;
        int index;
        TreeNode* node;
        WrapNode(int depth_,int index_,TreeNode* node_) :depth(depth_),index(index_),node(node_){}
    };
    struct Compare {
        bool operator()(const WrapNode& left, const WrapNode& right) {
            return left.depth > right.depth || (left.depth == right.depth && left.node->val > right.node->val);
        }
    };
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if (root == NULL) return {};
        vector<vector<int>>res;
        int addL = 0;
        priority_queue<WrapNode,vector<WrapNode>, Compare> queue_;
        queue_.emplace(0,0,root);
        while (!queue_.empty()) {
            auto wrapNode = queue_.top();
            queue_.pop();
            while (wrapNode.index + addL < 0) {
                res.insert(res.begin(), vector<int>());
                ++addL;
            }
            while (wrapNode.index + addL >= res.size())
                res.push_back({});
            res[wrapNode.index + addL].push_back(wrapNode.node->val);
            if (wrapNode.node->left != NULL)
                queue_.emplace(wrapNode.depth + 1, wrapNode.index - 1, wrapNode.node->left);
            if (wrapNode.node->right != NULL)
                queue_.emplace(wrapNode.depth + 1,wrapNode.index + 1, wrapNode.node->right);
        }
        return res;
    }
};